package jianzhiOffer;

import java.util.HashMap;
import java.util.Map;

class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class num07 {
    public Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for(int i = 0;i < len;i ++) {
            map.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,len - 1,0,len - 1);
    }
    public TreeNode myBuildTree(int[] preorder,int[] inorder,int p_left,int p_right,int i_left,int i_right) {
        if(p_left > p_right) {
            return null;
        }
        int root = p_left;
        int rootp = map.get(preorder[root]);
        int size = rootp - i_left;
        TreeNode node = new TreeNode(preorder[root]);
        node.left = myBuildTree(preorder,inorder,p_left + 1,p_left + size,i_left,rootp - 1);
        node.right = myBuildTree(preorder,inorder,p_left + size + 1,p_right,rootp + 1,i_right);
        return node;
    }
}
